Field of the Invention
This invention relates generally to a method for updating and extending digital vector maps using probe data, and more particularly toward a method for improving digital roadway and pathway maps using GPS coordinates generated by one or more personal navigation devices.
Related Art
Navigation systems, electronic maps (also known as digital maps), and geographical positioning devices are increasingly used by travelers to assist with various navigation functions, such as to determine the overall position and orientation of the traveler and/or vehicle, find destinations and addresses, calculate optimal routes, and provide real-time driving guidance. Typically, the navigation system includes a small display screen or graphic user interface that portrays a network of streets as a series of line segments, including a centre-line running approximately along the centre of each street or path. The traveler can then be generally located on the digital map close to or with regard to that centre-line.
Digital maps are expensive to produce and update, since exhibiting and processing road information is very costly. Surveying methods or digitizing satellite images are commonly employed techniques for creating a digital map. Furthermore, digital maps are likely to contain inaccuracies or systematic errors due to faulty or inaccurate input sources or flawed inference procedures. Once a digital map has been created, it is costly to keep map information up to date, since road geometry changes over time. In some regions of the world, digital maps are not available at all.
FIGS. 1A-1C depict a digital vector map in the form of roads. FIG. 1A represents major motorways or driving routes. FIG. 1B depicts the major motorways of FIG. 1A plus an interconnecting network of secondary roads. FIG. 1C illustrates all of the information of FIG. 1B together with an extended network of tertiary streets and alleys. As will be appreciated by reference to these figures, in combination with the expense and effort required to produce digital maps, it may be the case that an existing roadway map or network is incomplete in its depiction of all roadways or paths within a given region. Furthermore, due to the evolving nature of networks which may include but are not limited to roadways and paths, changes may occur over time such that an existing digital map may no longer accurately portray current conditions.
In FIG. 2, a digital vector map contains junctions J and line segments w1 . . . w9. Together, they constitute a graph with several additional properties. The junctions J are the nodes and the line segments w are the edges of the graph. For a unidirectional map the graph is directed and for a bidirectional map it is undirected. Every line segment w connects two junctions J. On the contrary, in each junction J meets just one or least three line segments w. (Only in exceptional cases will two line segments meet in a junction.) The junctions J and the line segments w are usually associated with several attributes, including for example weight value, measure and heading. The geometry of a line segment w is often described as a polygonal chain (also called polygonal curve, polygonal path, or piecewise linear curve). Alternatively one can also use other curves like splines, circle segments or clothoids. However because each curve can be sufficiently accurately approximated through a polygonal chain, usually polygonal chains are used. The vertices or nodes of a polygonal chain are called shape points SP because they define the shape of the curve. Of course, it is possible to change a shape point SP to a junction J under appropriate circumstances, for example if an attribute changes.
FIG. 2 illustrates a fractional section of a digital vector map, in this case a bidirectional roadway supporting two-way traffic. A main trunk of the roadway is indicated at 10 and a branch road extending generally perpendicularly from the main trunk 10 is indicated at 12. It is known, for example, to take probe data inputs from low-cost positioning systems and handheld devices and mobile phones with integrated GPS functionality for the purpose of incrementally learning a map using certain clustering technologies. The input to be processed consists of recorded GPS traces in the form of a standard ASCII stream, which is supported by almost all existing GPS devices. The output is a road map in the form of a directed graph with nodes and edges annotated with travel time information. Travelers appropriately fitted with navigation devices and traversing the main trunk 10 and branch 12 junction may thus create a trace map like that shown in FIG. 4, with nodes created at regular distances. The nodes and edges are stored in a digital vector map table or database. Through this technique which represents an incremental approach, road geometry can be inferred, and the collected data points refined by filtering and partitioning algorithms. For more complete discussion on this technique, reference is made to “Incremental Map Generaltion with GPS Traces,” Brüntrup, R., Edelkamp, S., Jabbar, S., Scholz, B., Proc. 8th Int. IEEE Conf. on Intelligent Transportation Systems, Vienna, Austria, 2005, Pages 413-418.
Another technique developed by H.-U. Otto and O. Schmelzle of Tele Atlas B. V., based on a local approach, generates a new road network from probe data. This approach is based on the technique of following each trace and looking into the buffer around separate trace points to establish the line segments. New network elements, e.g., roadways or pathways, are generated depending on the distribution of the data points inside the buffer and the associated directions of vectors. While this technique is useful in generating new maps using GPS traces or other probe data, it is not well suited to improving existing networks.
Accordingly, there is a need for an improved method to receive probe data such as that from GPS-enabled navigation devices, for the purpose of improving existing networks and generating new network elements such as employed in the practice of digital map making.